// @algorithm @lc id=893 lang=cpp 
// @title all-nodes-distance-k-in-binary-tree


// #define print(...)
// @test([3,5,1,6,2,0,8,null,null,7,4],5,2)=[7,4,1]
// @test([1],1,3)=[]
class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        // record parents
        unordered_map<int, TreeNode*> parents;
        parents[root->val] = NULL;
        print("target(", target, ")=", target->val, "\ntree=")
        function<void(TreeNode*)> IsParent = [&](TreeNode* node){
            print(node?(node->val==target->val?"["+to_string(node->val)+"]":to_string(node->val)):"-1", " ")
            if(!node) return;
            print(node->val==target->val ? (target=node,""):"")
            for(auto &p:{node->left, node->right}){
                print(!p ? "-1 " : "")
                if(!p) continue;
                parents[p->val] = node;
                IsParent(p);
            }
        };
        IsParent(root);
        print("\ntarget(", target, ")=", target->val, ", k=", k, "\n")
        // walk k from target to: left, right, parent
        vector<int> ans;
        function<void(TreeNode*,TreeNode*,int)> dfs = [&](TreeNode*from, TreeNode*cur, int dist){
            if(dist == k){
                print("from:", from->val, ", cur:", cur->val, "\n")
                ans.push_back(cur->val);
                return;
            }
            for(auto&p:{cur->left, cur->right, parents[cur->val]})
                if(p && p!=from) dfs(cur, p, 1+dist);
        };
        dfs(NULL, target, 0);
        return ans;
    }
};